﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0026_IsSymmetric : IAlgorithm
    {
        // 对称二叉树

        // 给定一个二叉树，检查它是否是镜像对称的。

        // 例如，二叉树[1, 2, 2, 3, 4, 4, 3] 是对称的。
        //      1
        //     / \
        //    2   2
        //   / \ / \
        //  3  4 4  3

        // 进阶：
        //  你可以运用递归和迭代两种方法解决这个问题吗？

        public void Test()
        {
            // 算法参数定义
            var tree = new TreeNode(2)
            {
                left = new TreeNode(1)
                {
                    left = new TreeNode(3),
                    right = new TreeNode(4)
                },
                right = new TreeNode(1)
                {
                    left = new TreeNode(4),
                    right = new TreeNode(3)
                }
            };
            // 算法执行与打印
            Console.WriteLine(IsSymmetric(tree));
        }

        // 算法
        public bool IsSymmetric(TreeNode root)
        {
            if (root == null)
                return true;
            return IsSymmetricHelp(root.left,root.right);
        }
        public bool IsSymmetricHelp(TreeNode left,TreeNode right)
        {
            if (left == null && right == null)
                return true;
            if (left == null || right == null || left.val != right.val)
                return false;
            return IsSymmetricHelp(left.left, right.right) && IsSymmetricHelp(right.left, left.right);
        }
    }
}
